/*
题目描述：找出数组中重复的数字
条件：
1. 长度为 n，范围 0 ~ n - 1
2. 选出任意一个重复的数字
方法：
1. 从头到尾扫描一遍   O(nlogn)
2. 使用哈希表        时间 O(n) 空间 O(n)
3. 遍历时将数字归为原位 时间 O(n) 空间 O(1)
    扫描下标为 i 的数 m时， 比较 m 与 n(n = num[m]) 的大小
    如果相等，说明找到了一个重复的元素，返回即可；
    如果不相等，就把这两个数(m 和 n)交换，让 m 回到属于它的位置(下标为 m)，再比较 n 和  num[n],
    直到找到最后的结果

增加条件：不改变原数组进行查找，长度为 n+1，范围为 1~n
方法:
4：增加一个辅助数组，然后采用方法3，需要辅助空间 O(n)
5: 改编二分查找   时间 O(nlogn), 空间 O(1)
    将 n个数一分为二，然后统计两半数字的出现次数，次数多的那一半一定存在重复的数字
    于是问题的规模就缩小了，只需要在次数多的那一半寻找重复元素即可，再继续一分为二，直到找到重复的元素为止
    notice: 这种方法不能找出所有重复的元素，比如[2,3,5,4,3,2,6,7],不能找出2， 因为在1~2范围内的数字出现了2次，3~4范围内数字也出现2次，但是这里选择了3~4范围
    打开方法 5 的debug即可观察到
 */

public class E3 {
    public static void main(String[] args){
        int[] num1 = {2,3,1,0,2,5,3};
        int[] num2 = {2,3,5,4,3,2,6,7};
        System.out.println("Before:");
        System.out.println("num1:");
        for(int a : num1){
            System.out.print(a + " ");
        }

        System.out.println();
        System.out.println("num2:");
        for(int a : num2){
            System.out.print(a + " ");
        }
        System.out.println();

        int res1 = duplicate(num1, num1.length);
        int res2 = getDuplication(num2, num2.length);

        System.out.println();
        System.out.println("result1 = " + res1);
        System.out.println("result2 = " + res2);
        System.out.println();

        System.out.println("After:");
        System.out.println("num1:");
        for(int a : num1){
            System.out.print(a + " ");
        }
        System.out.println();
        System.out.println("num2:");
        for(int a : num2){
            System.out.print(a + " ");
        }

    }

    //方法 3
    private static int duplicate(int[] num, int length){
        //check
        if(num == null || length <= 0){
            return -1;
        }
        for(int i = 0; i < length; i++){
            if(num[i] < 0 || num[i] > length - 1){
                return -1;
            }
        }

        for(int i = 0; i < length; i++){
            while(num[i] != i){
                if(num[i] == num[num[i]]){
                    return num[i];
                }
                int temp = num[i];
                num[i] = num[temp];
                num[temp] = temp;
            }
        }
        return -1;
    }

    //方法5：
    private static int getDuplication(final int[] num, int length){
        //check
        if(num == null || length <= 0){
            return -1;
        }
        int left = 1;//数字范围为 1~n
        int right = length - 1;//数组长度为 n + 1
        while(right >= left){
            int mid = left + (right - left) / 2;
            //debug
//            System.out.println("left = " + left + "  mid = " + mid + " right = " + right);
            int count = countRange(num, length, left, mid);
            if(right == left){
                if(count > 1){
                    return left;
                }
                else{
                    break;
                }
            }
            if(count > (mid - left + 1)){
                right = mid;
            }
            else{
                left = mid + 1;
            }

        }
        return -1;
    }
    private static int countRange(final int[] num, int length, int left, int right){
        if(num == null){
            return -1;
        }
        int count = 0;
        for(int i = 0; i < length; i++){
            if(num[i] >= left && num[i] <= right){
                count ++;
            }
        }
        return count;
    }
}
/*
Before:
num1:
2 3 1 0 2 5 3
num2:
2 3 5 4 3 2 6 7

result1 = 2
result2 = 3

After:
num1:
0 1 2 3 2 5 3
num2:
2 3 5 4 3 2 6 7
 */